// @algorithm @lc id=1250 lang=cpp 
// @title longest-common-subsequence


// @test("abcde","ace")=3
// @test("abc","abc")=3
// @test("abc","def")=0
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++)
                dp[i+1][j+1] = text1[i] == text2[j] ? 1 + dp[i][j]
                    : max(dp[i+1][j], dp[i][j+1]);
        }
        return dp[m][n];
    }
};